package com.zjsru.oneday202208;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author: likew
 * @Date: 2022/8/8
 * 特殊的二进制序列
 * 特殊的二进制序列是具有以下两个性质的二进制序列：(即交换的字串)
 * 0 的数量与 1 的数量相等。
 * 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
 * 给定一个特殊的二进制序列S，以字符串形式表示。定义一个操作 为首先选择S的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)
 * 在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？
 *
 *
 * 输入: S = "11011000"
 * 输出: "11100100"
 * 解释:
 * 将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。
 * 这是在进行若干次操作后按字典序排列最大的结果。
 *
 */
public class MakeLargestSpecial {
    public String makeLargestSpecial(String s) {
        if(s.length() == 0) {return s;}
        List<String> list = new ArrayList<>();
        char[] cs = s.toCharArray();
        for (int i = 0, j = 0, k = 0; i < cs.length; i++) {
            k += cs[i] == '1' ? 1 : -1;
            if(k == 0){
                list.add("1"+makeLargestSpecial(s.substring(j+1,i))+"0");
                j = i + 1;
            }
        }
        Collections.sort(list,(a,b) -> (b + a).compareTo(a + b));
        StringBuilder sb = new StringBuilder();
        for (String str:list) {
            sb.append(str);
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        MakeLargestSpecial makeLargestSpecial = new MakeLargestSpecial();
        String s = "11011000";
        System.out.println(makeLargestSpecial.makeLargestSpecial(s));
    }
}
